package 机试题16年;

import java.util.ArrayList;

/**
 * Created by hest0 on 2017/4/19.
 */
public class 汉诺塔问题1 {
    public static void main(String[] args) {
        System.out.println(new Hanoi().getSolution(3));
    }

    public static class Hanoi {
        public ArrayList<String> getSolution(int n) {
            ArrayList<String> result = new ArrayList<>();
            getSolCore(n, "left", "right", "mid", result);
            return result;
        }

        private void getSolCore(int n, String src, String des, String cache, ArrayList<String> res) {
            if (n <= 0) return;

            if (n == 1) {
                res.add("move from " + src + " to " + des);
                return;
            }

            getSolCore(n - 1, src, cache, des, res);
            res.add("move from " + src + " to " + des);
            getSolCore(n - 1, cache, des, src, res);
        }
    }
}
